"Running Up That Hill", bài hát đầu tiên Bush sáng tác cho album Hounds of Love, vốn có tựa đề là "A Deal with God". Vào mùa hè năm 1983 ở phòng thu âm tại nhà khi đó mới được nâng cấp của Bush, cô đã cho ra đời bài hát dưới dạng một bản thu âm thô trên chiếc băng 8 rãnh bằng cách sử dụng LinnDrum, Fairlight CMI và piano.[8] Giống như các bài hát khác trong album, ca khúc này được tiếp tục thực hiện trên chiếc băng ghi âm 8 rãnh ban đầu rồi sau đó chuyển sang hai chiếc băng master 24 rãnh để overdub. Phần hook thực hiện trên chiếc Fairlight được đặc biệt chú trọng, còn nhiều ý tưởng và thành phần tạo nên bài hát là những yếu tố đã có sẵn, trong đó có phần trống LinnDrum do Del Palmer lập trình, âm thanh "tiếng gió thổi trên xe lửa" và phần hát guide của Bush.[8]

Các đại diện của EMI Records bày tỏ sự lo ngại về khả năng đón nhận phản hồi tiêu cực từ các quốc gia sùng đạo nếu cho ra mắt bài hát dưới tựa đề "A Deal with God".[9] Bush nhượng bộ và đồng ý thay đổi tiêu đề bài hát. Tuy nhiên, tên bài hát trong album vẫn được ghi là "Running Up That Hill (A Deal with God)". Ban đầu, các giám đốc điều hành của EMI muốn phát hành "Cloudbusting" làm đĩa đơn mở đường cho Hounds of Love, nhưng Bush thuyết phục họ lựa chọn "Running Up That Hill" với lý do đây là bài hát đầu tiên được viết cho album và cô cảm thấy nó tái hiện một cách phổ quát hơn toàn album về mặt cảm xúc.

Bản thân bài hát thường bị hiểu sai. Chính Bush từng phát biểu:

Ý tôi là đàn ông và phụ nữ không bao giờ có thể thực sự thấu hiểu nhau, bởi lẽ đàn ông là đàn ông còn phụ nữ là phụ nữ. Nếu chúng ta thực sự có thể hoán đổi vị trí cho nhau, nếu chúng ta thực sự có thể ở trong thể xác của nhau một lúc, hẳn sẽ có rất nhiều điều bất ngờ! [Cười] Và tôi nghĩ làm như vậy sẽ giúp chúng ta thấu hiểu nhau tốt hơn. Tôi đã nghĩ rằng cách duy nhất để thực hiện điều đó chính là giao kèo với quỷ dữ. Và rồi tôi lại nghĩ, 'chà, giao ước với Chúa thì sao nhỉ!' Bạn biết đấy, theo một cách nào đó thì việc giao ước với Chúa nghe uy quyền hơn nhiều. Với tôi, ca khúc chỉ có một cái tên duy nhất là "Deal With God". Nhưng người ta bảo rằng nếu cứ giữ cái tên này thì bài hát sẽ không được phát ở bất kỳ quốc gia sùng đạo nào, Ý sẽ cấm cửa nó, Pháp sẽ cấm cửa nó và Úc cũng thế! Ireland cũng sẽ không cho phát bài hát này, thế nên nếu chúng tôi cứ cố chấp thì ca khúc có thể sẽ bị cấm chỉ vì có từ Chúa trong tên.[9][10]